package binarysearch;

import org.junit.Test;
import static org.junit.Assert.*;

public class BinSearchTemplate {
    int[] nums = {};
    int[] nums1 = {1};
    int[] nums11 = {1, 1};
    int[] nums12 = {1, 2};
    int[] nums123 = {1, 2, 3};
    int[] nums1224 = {1, 2, 2, 4};

    @Test
    public void testBinarySearch() {
        assertEquals(-1, binarySearch(nums, 0));
        assertEquals(-1, binarySearch(nums, 1));
        assertEquals(-1, binarySearch(nums, 2));
        assertEquals(-1, binarySearch(nums, 3));

        assertEquals(-1, binarySearch(nums1, 0));
        assertEquals(0, binarySearch(nums1, 1));
        assertEquals(-1, binarySearch(nums1, 2));
        assertEquals(-1, binarySearch(nums1, 3));

        assertEquals(-1, binarySearch(nums11, 0));
        assertTrue(0 == binarySearch(nums11, 1) || 1 == binarySearch(nums11, 1));
        assertEquals(-1, binarySearch(nums11, 2));
        assertEquals(-1, binarySearch(nums11, 3));

        assertEquals(-1, binarySearch(nums12, 0));
        assertEquals(0, binarySearch(nums12, 1));
        assertEquals(1, binarySearch(nums12, 2));
        assertEquals(-1, binarySearch(nums12, 3));

        assertEquals(-1, binarySearch(nums123, 0));
        assertEquals(0, binarySearch(nums123, 1));
        assertEquals(1, binarySearch(nums123, 2));
        assertEquals(2, binarySearch(nums123, 3));

        assertEquals(-1, binarySearch(nums1224, 0));
        assertEquals(0, binarySearch(nums1224, 1));
        assertTrue(1 == binarySearch(nums1224, 2) || 2 == binarySearch(nums1224, 2));
        assertEquals(-1, binarySearch(nums1224, 3));
        assertEquals(3, binarySearch(nums1224, 4));
        assertEquals(-1, binarySearch(nums1224, 5));
    }

    @Test
    public void testLeftBoundWhenExactlyMatchTrue() {
        boolean exactlyMatch = true;
        assertEquals(-1, leftBound(nums, 0, exactlyMatch));
        assertEquals(-1, leftBound(nums, 1, exactlyMatch));
        assertEquals(-1, leftBound(nums, 2, exactlyMatch));
        assertEquals(-1, leftBound(nums, 3, exactlyMatch));

        assertEquals(-1, leftBound(nums1, 0, exactlyMatch));
        assertEquals(0, leftBound(nums1, 1, exactlyMatch));
        assertEquals(-1, leftBound(nums1, 2, exactlyMatch));
        assertEquals(-1, leftBound(nums1, 3, exactlyMatch));

        assertEquals(-1, leftBound(nums11, 0, exactlyMatch));
        assertEquals(0, leftBound(nums11, 1, exactlyMatch));
        assertEquals(-1, leftBound(nums11, 2, exactlyMatch));
        assertEquals(-1, leftBound(nums11, 3, exactlyMatch));

        assertEquals(-1, leftBound(nums12, 0, exactlyMatch));
        assertEquals(0, leftBound(nums12, 1, exactlyMatch));
        assertEquals(1, leftBound(nums12, 2, exactlyMatch));
        assertEquals(-1, leftBound(nums12, 3, exactlyMatch));

        assertEquals(-1, leftBound(nums123, 0, exactlyMatch));
        assertEquals(0, leftBound(nums123, 1, exactlyMatch));
        assertEquals(1, leftBound(nums123, 2, exactlyMatch));
        assertEquals(2, leftBound(nums123, 3, exactlyMatch));
        assertEquals(-1, leftBound(nums123, 4, exactlyMatch));

        assertEquals(-1, leftBound(nums1224, 0, exactlyMatch));
        assertEquals(0, leftBound(nums1224, 1, exactlyMatch));
        assertEquals(1, leftBound(nums1224, 2, exactlyMatch));
        assertEquals(-1, leftBound(nums1224, 3, exactlyMatch));
        assertEquals(3, leftBound(nums1224, 4, exactlyMatch));
        assertEquals(-1, leftBound(nums1224, 5, exactlyMatch));
    }

    @Test
    public void testLeftBoundWhenExactlyMatchFalse() {
        boolean exactlyMatch = false;
        assertEquals(0, leftBound(nums, 0, exactlyMatch));
        assertEquals(0, leftBound(nums, 1, exactlyMatch));
        assertEquals(0, leftBound(nums, 2, exactlyMatch));
        assertEquals(0, leftBound(nums, 3, exactlyMatch));

        assertEquals(0, leftBound(nums1, 0, exactlyMatch));
        assertEquals(0, leftBound(nums1, 1, exactlyMatch));
        assertEquals(1, leftBound(nums1, 2, exactlyMatch));
        assertEquals(1, leftBound(nums1, 3, exactlyMatch));

        assertEquals(0, leftBound(nums11, 0, exactlyMatch));
        assertEquals(0, leftBound(nums11, 1, exactlyMatch));
        assertEquals(2, leftBound(nums11, 2, exactlyMatch));
        assertEquals(2, leftBound(nums11, 3, exactlyMatch));

        assertEquals(0, leftBound(nums12, 0, exactlyMatch));
        assertEquals(0, leftBound(nums12, 1, exactlyMatch));
        assertEquals(1, leftBound(nums12, 2, exactlyMatch));
        assertEquals(2, leftBound(nums12, 3, exactlyMatch));

        assertEquals(0, leftBound(nums123, 0, exactlyMatch));
        assertEquals(0, leftBound(nums123, 1, exactlyMatch));
        assertEquals(1, leftBound(nums123, 2, exactlyMatch));
        assertEquals(2, leftBound(nums123, 3, exactlyMatch));
        assertEquals(3, leftBound(nums123, 4, exactlyMatch));

        assertEquals(0, leftBound(nums1224, 0, exactlyMatch));
        assertEquals(0, leftBound(nums1224, 1, exactlyMatch));
        assertEquals(1, leftBound(nums1224, 2, exactlyMatch));
        assertEquals(3, leftBound(nums1224, 3, exactlyMatch));
        assertEquals(3, leftBound(nums1224, 4, exactlyMatch));
        assertEquals(4, leftBound(nums1224, 5, exactlyMatch));
    }

    @Test
    public void testRightBoundWhenExactlyMatchTrue() {
        boolean exactlyMatch = true;
        assertEquals(-1, rightBound(nums, 0, exactlyMatch));
        assertEquals(-1, rightBound(nums, 1, exactlyMatch));
        assertEquals(-1, rightBound(nums, 2, exactlyMatch));
        assertEquals(-1, rightBound(nums, 3, exactlyMatch));

        assertEquals(-1, rightBound(nums1, 0, exactlyMatch));
        assertEquals(0, rightBound(nums1, 1, exactlyMatch));
        assertEquals(-1, rightBound(nums1, 2, exactlyMatch));
        assertEquals(-1, rightBound(nums1, 3, exactlyMatch));

        assertEquals(-1, rightBound(nums11, 0, exactlyMatch));
        assertEquals(1, rightBound(nums11, 1, exactlyMatch));
        assertEquals(-1, rightBound(nums11, 2, exactlyMatch));
        assertEquals(-1, rightBound(nums11, 3, exactlyMatch));

        assertEquals(-1, rightBound(nums12, 0, exactlyMatch));
        assertEquals(0, rightBound(nums12, 1, exactlyMatch));
        assertEquals(1, rightBound(nums12, 2, exactlyMatch));
        assertEquals(-1, rightBound(nums12, 3, exactlyMatch));

        assertEquals(-1, rightBound(nums123, 0, exactlyMatch));
        assertEquals(0, rightBound(nums123, 1, exactlyMatch));
        assertEquals(1, rightBound(nums123, 2, exactlyMatch));
        assertEquals(2, rightBound(nums123, 3, exactlyMatch));
        assertEquals(-1, rightBound(nums123, 4, exactlyMatch));

        assertEquals(-1, rightBound(nums1224, 0, exactlyMatch));
        assertEquals(0, rightBound(nums1224, 1, exactlyMatch));
        assertEquals(2, rightBound(nums1224, 2, exactlyMatch));
        assertEquals(-1, rightBound(nums1224, 3, exactlyMatch));
        assertEquals(3, rightBound(nums1224, 4, exactlyMatch));
        assertEquals(-1, rightBound(nums1224, 5, exactlyMatch));
    }

    @Test
    public void testRightBoundWhenExactlyMatchFalse() {
        boolean exactlyMatch = false;
        assertEquals(-1, rightBound(nums, 0, exactlyMatch));
        assertEquals(-1, rightBound(nums, 1, exactlyMatch));
        assertEquals(-1, rightBound(nums, 2, exactlyMatch));
        assertEquals(-1, rightBound(nums, 3, exactlyMatch));

        assertEquals(-1, rightBound(nums1, 0, exactlyMatch));
        assertEquals(0, rightBound(nums1, 1, exactlyMatch));
        assertEquals(0, rightBound(nums1, 2, exactlyMatch));
        assertEquals(0, rightBound(nums1, 3, exactlyMatch));

        assertEquals(-1, rightBound(nums11, 0, exactlyMatch));
        assertEquals(1, rightBound(nums11, 1, exactlyMatch));
        assertEquals(1, rightBound(nums11, 2, exactlyMatch));
        assertEquals(1, rightBound(nums11, 3, exactlyMatch));

        assertEquals(-1, rightBound(nums12, 0, exactlyMatch));
        assertEquals(0, rightBound(nums12, 1, exactlyMatch));
        assertEquals(1, rightBound(nums12, 2, exactlyMatch));
        assertEquals(1, rightBound(nums12, 3, exactlyMatch));

        assertEquals(-1, rightBound(nums123, 0, exactlyMatch));
        assertEquals(0, rightBound(nums123, 1, exactlyMatch));
        assertEquals(1, rightBound(nums123, 2, exactlyMatch));
        assertEquals(2, rightBound(nums123, 3, exactlyMatch));
        assertEquals(2, rightBound(nums123, 4, exactlyMatch));

        assertEquals(-1, rightBound(nums1224, 0, exactlyMatch));
        assertEquals(0, rightBound(nums1224, 1, exactlyMatch));
        assertEquals(2, rightBound(nums1224, 2, exactlyMatch));
        assertEquals(2, rightBound(nums1224, 3, exactlyMatch));
        assertEquals(3, rightBound(nums1224, 4, exactlyMatch));
        assertEquals(3, rightBound(nums1224, 5, exactlyMatch));
    }

    public static int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else { // nums[mid] == target
                return mid;
            }
        }
        return -1; // not found
    }

    /**
     * if exactlyMatch is true,
     * return the minimal index i, where nums[i] = target;
     * return -1 if no such index.
     *
     * if exactlyMatch is false,
     * return the minimal index i, where nums[i] >= target; e.g. nums=[1, 2, 2, 4], target=2, return 1.
     * return nums.length, if for any j, nums[j] < target; e.g. nums=[1, 2, 2, 4], target=5, return 4 (as if there is +INF at tail).
     * return 0, if for any j, nums[j] >= target; e.g. nums=[1, 2, 2, 4], target=0, return 0.
     */
    public static int leftBound(int[] nums, int target, boolean exactlyMatch) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else { // nums[mid] == target
                right = mid - 1;
            }
        }

        if (exactlyMatch) {
            if (left >= nums.length) {
                // target > nums[length-1]
                return -1;
            }
            if (nums[left] != target) {
                // target not in nums
                return -1;
            }
        }
        return left; // might be nums.length
    }

    /**
     * if exactlyMatch is true,
     * return the maximal index i, where nums[i] = target;
     * return -1 if no such index.
     *
     * if exactlyMatch is false,
     * return the maximal index i, where nums[i] <= target; e.g. nums=[1, 2, 2, 4], target=2, return 2.
     * return -1, if for any j, nums[j] > target; e.g. nums=[1, 2, 2, 4], target=0, return -1 (as if there is -INF at head).
     * return nums.length-1, if for any j, nums[j] <= target; e.g. nums=[1, 2, 2, 4], target=5, return 3.
     */
    public static int rightBound(int[] nums, int target, boolean exactlyMatch) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else { // nums[mid] == target
                left = mid + 1;
            }
        }

        if (exactlyMatch) {
            if (right < 0) {
                return -1;
            }
            if (nums[right] != target) {
                return -1;
            }
        }
        return right; // might be -1
    }
}
